package double_pointer;

/**
 * @Description 剑指 Offer 52. 两个链表的第一个公共节点(相交链表)
 * @Author Firenut
 * @Date 2023-01-21 19:02
 */
public class T52_getIntersectionNode {
    // 实在不行就记住这个结论(细节别出错)
    // 先让p1指向headA,p2指向headB,然后逐个遍历链表的结点,当p1走到链表的尾部,就让其指向p2;
    // 当p2走到链表的尾部,就让其指向p1,这样的话,p1和p2必然会在交点相遇: 因为a+(b-c) = b+(a-c) <==> a+b = b+a(画图很直观就可以看出来)
    // 感觉有点数学的意思
    // 设链表A长度为A,链表B长度为B,公共长度为C,当p1、p2相遇的时候(也有可能是p1==p2==null)
    // 如果c==0,说明两个链表之间没有公共结点
    // 如果c>0,说明两个链表之间有公共结点
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1, p2;
        p1 = headA;
        p2 = headB;
        while (p1 != p2) {
            p1 = p1 != null ? p1.next : headB;
            p2 = p2 != null ? p2.next : headA;
            // 一上来应该先判断不为null,才有指向next的操作,不让循环条件永远出不去的
            // 这样写有问题,如果本身两个链表就没有相交，那么当p1,p2同时为null时,那么会有p1 = headB;p2=headA,所以每次循环的判断条件都不会成立的!
            // ---------
            // p1=p1.next;
            // p2=p2.next;
            /*if (p1 == null) {
                p1 = headB;
            }
            if (p2 == null) {
                p2 = headA;
            }*/
        }
        return p1;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
      val = x;
      next = null;
    }
}